{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "file_path = 'Data.txt'\n",
    "out_path = 'basic_result.txt'\n",
    "\n",
    "# 打开并读取文件\n",
    "with open(file_path, 'r') as f:\n",
    "    lines = f.readlines()\n",
    "\n",
    "degree = []\n",
    "max_node_id = 0\n",
    "max_to_id = 0\n",
    "matrix = {}\n",
    "dead_ends = []\n",
    "\n",
    "# 遍历每一行\n",
    "for line in lines:\n",
    "    # 分割行并将结果添加到列表中\n",
    "    from_node_id, to_node_id = map(int, line.split())\n",
    "    if(from_node_id > max_node_id): # 如果from_node_id大于max_node_id，说明有新的节点出现 \n",
    "        for i in range(max_node_id, from_node_id ):\n",
    "            matrix[i] = [] # 初始化新节点的邻接表\n",
    "            degree.append(0)\n",
    "        max_node_id = from_node_id\n",
    "    \n",
    "    if(to_node_id > max_to_id):\n",
    "        max_to_id = to_node_id\n",
    "        \n",
    "    degree[from_node_id - 1] += 1\n",
    "    matrix[from_node_id - 1].append(to_node_id - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_nums = max(max_node_id, max_to_id) \n",
    "dead_ends = [i for i in range(node_nums) if degree[i] == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "diff: 9.049418438325928e-05\n"
     ]
    }
   ],
   "source": [
    "from IPython.display import clear_output\n",
    "rank_old = np.ones(node_nums) / node_nums\n",
    "d = 0.85\n",
    "epsilon = 1e-8\n",
    "\n",
    "while True:\n",
    "    rank_new = np.ones(node_nums) * (1 - d) / node_nums\n",
    "    rank_new += np.sum([rank_old[i]for i in dead_ends])* d /node_nums\n",
    "    #两种处理dead_end的方式，一次性处理所有dead ends，或者每次迭代都进行判断处理\n",
    "\n",
    "    for i in range(node_nums):\n",
    "        for j in matrix[i]: \n",
    "            rank_new[j] += d * rank_old[i] / degree[i]\n",
    "        \n",
    "    diff = np.abs(rank_new - rank_old).sum()\n",
    "    if diff < node_nums*epsilon:\n",
    "        break\n",
    "\n",
    "    clear_output(wait=True)\n",
    "    print(f\"diff: {diff}\")\n",
    "    \n",
    "    rank_old = rank_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index: 2730, Value: 0.0008714137859396278\n",
      "Index: 7102, Value: 0.0008540935774449336\n",
      "Index: 1010, Value: 0.0008491780767153843\n",
      "Index: 368, Value: 0.0008354730268571668\n",
      "Index: 1907, Value: 0.0008301661447518154\n",
      "Index: 7453, Value: 0.0008202343300680923\n",
      "Index: 4583, Value: 0.0008174658880004726\n",
      "Index: 7420, Value: 0.0008099185634202566\n",
      "Index: 1847, Value: 0.0008095910301479806\n",
      "Index: 5369, Value: 0.000805592543560131\n",
      "Index: 3164, Value: 0.0008046822790861683\n",
      "Index: 7446, Value: 0.0008027497128716405\n",
      "Index: 3947, Value: 0.0008018181860008154\n",
      "Index: 2794, Value: 0.0007919193649553847\n",
      "Index: 3215, Value: 0.0007817767134876385\n",
      "Index: 5346, Value: 0.0007808069646938417\n",
      "Index: 7223, Value: 0.0007769753201734471\n",
      "Index: 630, Value: 0.0007739891892213758\n",
      "Index: 4417, Value: 0.0007684350755836879\n",
      "Index: 4955, Value: 0.0007604058261171739\n",
      "Index: 3208, Value: 0.0007586423700990547\n",
      "Index: 2902, Value: 0.0007571633605248535\n",
      "Index: 5671, Value: 0.0007554744486563804\n",
      "Index: 5833, Value: 0.000751288633409423\n",
      "Index: 5553, Value: 0.0007475833198907554\n",
      "Index: 8096, Value: 0.00074703044381002\n",
      "Index: 3204, Value: 0.0007453961304891346\n",
      "Index: 758, Value: 0.0007445711657445823\n",
      "Index: 6301, Value: 0.000744210005331788\n",
      "Index: 5769, Value: 0.00074079690024291\n",
      "Index: 8194, Value: 0.0007397325222336752\n",
      "Index: 4957, Value: 0.0007376708913285219\n",
      "Index: 8060, Value: 0.0007360086218717702\n",
      "Index: 7938, Value: 0.0007334811572109561\n",
      "Index: 5584, Value: 0.0007327724858574148\n",
      "Index: 6568, Value: 0.0007323065133683284\n",
      "Index: 1430, Value: 0.0007321843677065387\n",
      "Index: 7250, Value: 0.0007309834032379424\n",
      "Index: 3185, Value: 0.0007301226485545056\n",
      "Index: 2737, Value: 0.0007259002503408867\n",
      "Index: 3751, Value: 0.0007254722175346037\n",
      "Index: 150, Value: 0.0007254623218068503\n",
      "Index: 5099, Value: 0.0007208780033082647\n",
      "Index: 2944, Value: 0.0007170090200009662\n",
      "Index: 7872, Value: 0.0007150769526537927\n",
      "Index: 2639, Value: 0.0007136358713756499\n",
      "Index: 5074, Value: 0.0007136121318378158\n",
      "Index: 1034, Value: 0.0007126608885350505\n",
      "Index: 229, Value: 0.0007120146850260534\n",
      "Index: 6648, Value: 0.0007116666890727263\n",
      "Index: 4222, Value: 0.0007098948889517298\n",
      "Index: 7406, Value: 0.000709294282169319\n",
      "Index: 2464, Value: 0.0007089904505395025\n",
      "Index: 3578, Value: 0.0007088120653618903\n",
      "Index: 930, Value: 0.0007080026177887021\n",
      "Index: 6777, Value: 0.0007078878843602235\n",
      "Index: 2484, Value: 0.0007045990553899922\n",
      "Index: 4944, Value: 0.0007007810591846453\n",
      "Index: 1197, Value: 0.0006994816492666336\n",
      "Index: 3221, Value: 0.0006987253983041837\n",
      "Index: 2041, Value: 0.0006982569375722983\n",
      "Index: 7579, Value: 0.0006975476267000943\n",
      "Index: 6787, Value: 0.0006972322184974256\n",
      "Index: 6530, Value: 0.0006964627253017166\n",
      "Index: 8112, Value: 0.0006961736303552946\n",
      "Index: 6005, Value: 0.0006958032936524917\n",
      "Index: 6190, Value: 0.0006955241867884879\n",
      "Index: 5655, Value: 0.0006948295375581997\n",
      "Index: 251, Value: 0.0006937759432871052\n",
      "Index: 3951, Value: 0.0006929348363573944\n",
      "Index: 8018, Value: 0.0006923885742204045\n",
      "Index: 233, Value: 0.0006917479212756466\n",
      "Index: 2589, Value: 0.0006912252321428882\n",
      "Index: 5996, Value: 0.0006911235633472937\n",
      "Index: 482, Value: 0.0006908267232700543\n",
      "Index: 972, Value: 0.000690099042858118\n",
      "Index: 7499, Value: 0.0006863479935488293\n",
      "Index: 7442, Value: 0.0006860297505491394\n",
      "Index: 1173, Value: 0.0006855662798029936\n",
      "Index: 2369, Value: 0.0006849826076478034\n",
      "Index: 6315, Value: 0.0006833085543359093\n",
      "Index: 5129, Value: 0.00068310630960749\n",
      "Index: 7784, Value: 0.0006828967351106184\n",
      "Index: 5998, Value: 0.000682684364276397\n",
      "Index: 4692, Value: 0.0006824763674358298\n",
      "Index: 4255, Value: 0.0006824372471686089\n",
      "Index: 6692, Value: 0.0006820009009692969\n",
      "Index: 4832, Value: 0.0006816214190243352\n",
      "Index: 5275, Value: 0.000679866909645045\n",
      "Index: 5376, Value: 0.0006792710853897304\n",
      "Index: 2232, Value: 0.0006772922181264855\n",
      "Index: 6928, Value: 0.0006765547461563111\n",
      "Index: 260, Value: 0.0006752840006489068\n",
      "Index: 1677, Value: 0.0006751795892029621\n",
      "Index: 6847, Value: 0.0006735968311919978\n",
      "Index: 6883, Value: 0.0006731140510828921\n",
      "Index: 7702, Value: 0.0006730776389957356\n",
      "Index: 1798, Value: 0.0006722509491725342\n",
      "Index: 4681, Value: 0.0006712059416513803\n",
      "Index: 2664, Value: 0.0006704377117612959\n"
     ]
    }
   ],
   "source": [
    "top_indices = np.argsort(rank_new)[::-1][:100]\n",
    "top_values = rank_new[top_indices]\n",
    "\n",
    "for i in range(100):\n",
    "    print(f\"Index: {top_indices[i] + 1}, Value: {top_values[i]}\")\n",
    "\n",
    "with open(out_path, 'w') as f:\n",
    "    for i in range(100):\n",
    "        f.write(f\"{top_indices[i] + 1} {top_values[i]}\\n\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
